package net.xuele.learn.dancing.dp;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: yubo
 * @date: 11:03 2020/12/28
 * @Description: 类描述：leetcode 77编辑距离
 */

public class MinDistance {

    int minDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        // 二维数组dp表示的是word1到i位置转换成word2到j位置需要最少步数
        // n+1考虑的是空字符串的情况
        int[][] dp = new int[m + 1][n + 1];
        // base case
        dp[0][0] = 0;
        for (int i = 1; i <= m; i++) {
            //0 表示的是空字符串
            dp[i][0] = i;
        }

        for (int j = 1; j <= n; j++) {
            // 0表示的是空字符串
            dp[0][j] = j;
        }
        // 自底向上求解
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(
                            // 删除操作，表示dp[i][j]由dp[i-1]dp[j]进行一步删除操作得到的
                            dp[i - 1][j] + 1,
                            // 插入操作，表示dp[i][j]由dp[i]dp[j-1]进行一步插入操作得到的
                            dp[i][j - 1] + 1,
                            // 替换操作，dp[i][j]由dp[i-1]dp[j-1]进行一步替换操作操作得到的
                            dp[i - 1][j - 1] + 1
                    );
                }
            }
        }
        // 储存着整个 s1 和 s2 的最小编辑距离
        return dp[m][n];
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }


    public String[] permutation(String S) {
        Set<String> res = new HashSet<>();
        combination(res, S, new StringBuilder(), new boolean[S.length()]);
        return res.toArray(new String[res.size()]);
    }

    private void combination(Set<String> res, String s, StringBuilder sb, boolean[] marked) {
        if (sb.length() == s.length()) {
            res.add(sb.toString());
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (!marked[i]) {
                marked[i] = true;
                sb.append(s.charAt(i));
                // 经典回溯
                combination(res, s, sb, marked);
                sb.deleteCharAt(sb.length() - 1);
                marked[i] = false;
            }
        }
    }
}
